This invention relates to deadlock detection mechanisms for distributed data processing systems.
In a database system it is common to increase performance by allowing multiple transactions to execute concurrently. In order to ensure data consistency, a transaction must lock a data resource before accessing it and unlock it afterwards, and transactions must conform to the two-phase locking protocol. Two-phase locking means that a transaction must take all of its locks before it can release any of its locks (the first phase consists of taking locks, the second phase of releasing locks).
Locking introduces dependencies between transactions: that is, one transaction may be waiting for another transaction to release a lock before it can proceed. If a cyclic chain of dependencies occurs, all the transactions in the chain will be held up, each waiting for another; this is referred to as a deadlock. A mechanism must therefore be provided to detect deadlocks, and to perform appropriate action to break a detected deadlock. This action may involve selecting one of the deadlocked transactions as a victim, and aborting it. Deadlock detection is sometimes performed by a database management system back-end and sometimes by a platform-specific program.
Deadlock detection mechanisms are sometimes called upon to detect forms of deadlock other than that created by data resource locking. In these cases, the two-phase locking protocol may not be followed. The fact that modern database management system backends are multi-threaded means that a transaction might take and release a lock a number of times during its execution. This may cause spurious deadlocks to be detected by conventional deadlock detection mechanisms.
The object of the present invention is to provide a deadlock detection mechanism which enables such spurious deadlocks to be avoided.